/*
 * @lc app=leetcode.cn id=69 lang=javascript
 *
 * [69] x 的平方根 
 */

// @lc code=start
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x === 0) return x;

    let l = 1, r = x
    while (l <= r) {
        const mid = l + ((r - l) >> 1);
        const sqrt = x / mid;
        if (sqrt === mid) {
            return mid;
        }
        else if (mid > sqrt) {
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return r
};


/*
 * 牛顿法
 * https://www.zhihu.com/question/20690553
 * 其公式为 xn+1 = xn − f (xn)/ f ′(xn)。
 * 给定 f (x) = x^2 − a = 0，
 * 这里的迭代公式为 xn+1 = (xn + a / xn) / 2
 */

var mySqrt = function(x) {
    let a = x
    while(a * a > x) {
        a = Math.floor((a + x / a) / 2);
    }
    return a
}
// @lc code=end

console.log(
    mySqrt(6)
)